/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/n-queens
   @Language: C++
   @Datetime: 16-02-09 08:18
   */

class Solution {
	vector<vector<string> > solves;
	bool isValid(vector<int> &board,int row,int col){
		for(int i=0; i<row; ++i)
			if (board[i]==col || board[i]+row-i==col || board[i]-row+i==col)
				return false;
		return true;
	}
	void NQueen(vector<int> &board,int N,int pos){
		if (pos==N){
			vector<string> vs(N,string(N,'.'));
			for(int i=0; i<N; vs[i][board[i]]='Q', ++i);
			solves.push_back(vs);
			return;
		}
		for(int i=0; i<N; ++i){
			board[pos]=i;
			if (isValid(board,pos,i)) NQueen(board,N,pos+1);
		}
	}

public:
	/**
	 * Get all distinct N-Queen solutions
	 * @param n: The number of queens
	 * @return: All distinct solutions
	 * For example, A string '...Q' shows a queen on forth position
	 */
	vector<vector<string> > solveNQueens(int n) {
		// write your code here
		vector<int> board(n,-1);
		solves.clear();
		NQueen(board,n,0);
		return solves;
	}
};
